package com.itheima.search;

public class A03_BlockSearchDemo1 {
    public static void main(String[] args) {
         /*
            分块查找
            核心思想：
                块内无序，块间有序
            实现步骤：
                1.创建数组blockArr存放每一个块对象的信息
                2.先查找blockArr确定要查找的数据属于哪一块
                3.再单独遍历这一块数据即可
        */
        int[] arr = {16, 5, 9, 12, 21, 18,
                32, 23, 37, 26, 45, 34,
                50, 48, 61, 52, 73, 66};

        //创建三个Block对象
        Block1 b1 = new Block1(21, 0, 5);
        Block1 b2 = new Block1(45, 6, 11);
        Block1 b3 = new Block1(73, 12, 17);

        //定义一个变量用来记录要查找的元素
        int number = 37;

        //创建一个Block对象的数组用来管理三个块的对象（索引表）
        Block1[] blockArr = {b1, b2, b3};

        //调用方法，传递索引表，数组，要查找的元素
        int index = getIndex(blockArr, arr, number);

        //打印一下
        System.out.println(index);
    }

    //利用分块查找的原理，查询number的索引

    public static int getIndex(Block1[] blockArr, int[] arr, int number) {
        //1.确定number是在哪一块当中
        int index = findIndexBlock(blockArr, number);

        if (index < 0) {
            //表示number不在数组当中
            return -1;
        }

        //2.获取这一块的起始索引和结束索引
        int startIndex = blockArr[index].getStartindex();
        int endIndex = blockArr[index].getEndindex();

        //3.遍历
        for (int i = startIndex; i <= endIndex; i++) {
            if (arr[i] == number) {
                return i;
            }
        }
        return -1;
    }

    //定义一个方法，用来确定number在哪一块当中
    public static int findIndexBlock(Block1[] blockArr, int number) {
        //Block b1 = new Block(21,0,5);   ----0
        //Block b2 = new Block(45,6,11);  ----1
        //Block b3 = new Block(73,12,17); ----2

        //从0索引开始遍历blockArr，如果number小于max，那么就表示number是在这一块当中的
        for (int i = 0; i < blockArr.length; i++) {
            if (blockArr[i].getMax() > number) {
                return i;
            }
        }
        return -1;
    }
}

class Block1 {
    private int max;
    private int startindex;
    private int endindex;

    public Block1() {
    }

    public Block1(int max, int startindex, int endindex) {
        this.max = max;
        this.startindex = startindex;
        this.endindex = endindex;
    }

    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public int getStartindex() {
        return startindex;
    }

    public void setStartindex(int startindex) {
        this.startindex = startindex;
    }

    public int getEndindex() {
        return endindex;
    }

    public void setEndindex(int endindex) {
        this.endindex = endindex;
    }
}
